package com.asa.jihe;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.asa.jihe.utils.Graph;
import com.asa.jihe.utils.Line;
import com.asa.jihe.utils.Point;
import com.asa.jihe.utils.ToLeftTest;
import com.asa.numanaly.F;

/**
 * 相交图
 * 判断一个平面上面，相交的由线连成的集合图形 有点写不动
 * 我们的目标是给神经网络做后勤
 * 
 * @author asa
 *
 */
public class TuXinXiangJiao {

	public static void main(String[] args) {

		List<Graph> initdate = initdate();

		System.out.println(initdate.size());

		Graph graph0 = initdate.get(0);
		Graph graph1 = initdate.get(1);
//
//		// 判断两个图形是否相交
//		for (int i = 0; i < initdate.size(); i++) {
//			System.out.println(initdate.get(i));
//		}
//
//		boolean asa = graphxiangjiao(graph0, graph1);
//
//		System.out.println(asa);
//
//		boolean asa2 = graphxiangjiao2(graph0, graph1);
//		System.out.println(asa2);


		
		
		
//		getjiaodian(graph0.lines.get(1), graph1.lines.get(1));
		
//		Line line1 = new Line();
//		Line line2 = new Line();
//		line1.spoint = new Point();
//		line1.epoint = new Point();
//		line2.spoint = new Point();
//		line2.epoint = new Point();
//		line1.spoint.x = 0;
//		line1.spoint.y = 2;
//		line1.epoint.x = 2;
//		line1.epoint.y = 1;
//		
//		line2.spoint.x = 1;
//		line2.spoint.y = 1;
//		line2.epoint.x = 3;
//		line2.epoint.y = 2;
//		
//		
//		getjiaodian(line1, line2);
		
		
		//求两个图的交图
		List<Line> lines0 = graph0.lines;
		nishizhen(lines0);//
		
		List<Line> lines1 = graph1.lines;
		nishizhen(lines1);//

		boolean isnihsizheng0 = isnihsizheng(lines0);
		boolean isnihsizheng1= isnihsizheng(lines0);
		System.out.println(isnihsizheng0);
		System.out.println(isnihsizheng1);
		
		
		//思路是，两个图的交，必定有交点是两条图交图的顶点，一个图的点，包含于另一个图内，那么这个点也必然是交图的顶点
		//由这两类点所构成的图就是交图了
		List<Point> graphjiaoji = graphjiaoji(graph0, graph1);

		System.out.println(graphjiaoji.size());
		
		for (int i = 0; i < graphjiaoji.size(); i++) {
			System.out.println(graphjiaoji.get(i));
		}
		
		
	}




/**
 * 使图形逆时针
 * @param lines
 */
	public static void nishizhen(List<Line> lines) {
		boolean leftTest = isnihsizheng(lines);
		
		System.out.println(leftTest);
		
		if (!leftTest) {//这个是false，那么就是顺时针的
			reversepoint(lines);	
		}
	}

	
	
	

	/**
	 * 逆转图中线的次序，顺时针就变逆时针，逆时针就变顺时针
	 * @param lines
	 */
	private static void reversepoint(List<Line> lines) {
		Collections.reverse(lines);
		for (int i = 0; i < lines.size(); i++) {
			Point buffpoint = lines.get(i).spoint;
			lines.get(i).spoint = lines.get(i).epoint;
			lines.get(i).epoint = buffpoint;

		}
	}



	/**
	 * 判断线的连接是不是逆时针的
	 * @param lines
	 * @return
	 */
	public static boolean isnihsizheng(List<Line> lines) {
		List<Point> lishizheng = new ArrayList<Point>();
		for (int i = 0; i < 2; i++) {
			
			boolean contains = lishizheng.contains(lines.get(i).spoint);
			if (!contains) {
				lishizheng.add(lines.get(i).spoint);
			}
			contains = lishizheng.contains(lines.get(i).epoint);
			if (!contains) {
				lishizheng.add(lines.get(i).epoint);
			}
		}
		
		boolean leftTest = ToLeftTest.toLeftTest(lishizheng.get(0), lishizheng.get(1), lishizheng.get(2));
		return leftTest;
	}

	
	
	
	/**
	 * 两个图片的交集图
	 * @param graph0
	 * @param graph1
	 * @return
	 */
	public static List<Point> graphjiaoji(Graph graph0, Graph graph1) {
		// TODO Auto-generated method stub

		// 先用最SB的方法啊
		List<Line> lines0 = graph0.lines;
		List<Line> lines1 = graph1.lines;
		
		Map<Point, String> piontmap = new HashMap<>();

		for (int j = 0; j < lines1.size(); j++) {
	
			Line line = lines1.get(j);
			Point spoint = line.spoint;
			Point epoint = line.epoint;		
			boolean leftTestS = ToLeftTest.containtpoint(spoint, lines0);

			boolean leftTestE = ToLeftTest.containtpoint(epoint, lines0);

			//这条线段的起始点和终点都在另一个图内
			if (leftTestS) {
				piontmap.put(spoint, j+"");
			}

			if (leftTestE) {
				piontmap.put(epoint, j+"");
			}
			

		}
		
		for (int j = 0; j < lines0.size(); j++) {
			
			Line line = lines0.get(j);
			Point spoint = line.spoint;
			Point epoint = line.epoint;		
			boolean leftTestS = ToLeftTest.containtpoint(spoint, lines1);

			boolean leftTestE = ToLeftTest.containtpoint(epoint, lines1);

			//这条线段的起始点和终点都在另一个图内
			if (leftTestS) {
				piontmap.put(spoint, j+"");
			}

			if (leftTestE) {
				piontmap.put(epoint, j+"");
			}
			

		}
		
		
		for (int j = 0; j < lines1.size(); j++) {
			Line line = lines1.get(j);
			for (int i = 0; i < lines0.size(); i++) {
				
				Line line0 = lines0.get(i);
				
				boolean jiaocha = JiHeQiuJiao.jiaocha(line, line0);
				
				if (jiaocha) {
					
					Point point = getjiaodian(line, line0);
					
					piontmap.put(point, j+"");

				}
				
			}

		}

		
		List<Point> keylist = new ArrayList<>(piontmap.keySet());

		return keylist;

		
		

	}
	
	
	
	
	/*
	 * 求两条线端的交点，这个是要肯定有交点的
	 * 里面最后算的是两条直线的交点，所以调用这个方法前，必须保证两个线是相交的
	 * 
	 * 里面要去考虑水平线和垂直线，汗！！！
	 */
	public static Point getjiaodian(Line line1,Line line2) {
		System.out.println(line1);
		System.out.println(line2);
		Point spoint1 = line1.spoint;
		Point epoint1 = line1.epoint;
		
		Point spoint2 = line2.spoint;
		Point epoint2 = line2.epoint;
		double a1 = 1;
		if (spoint1.x!=epoint1.x) {
			a1 = (spoint1.y-epoint1.y)/(spoint1.x-epoint1.x);
		}
		double a2 = 1;
		if (spoint2.x!=epoint2.x) {
			a2 = (spoint2.y-epoint2.y)/(spoint2.x-epoint2.x);
		}
		
		double b1 = 0;
		if (spoint1.x!=epoint1.x) {
		    b1 = spoint1.y - a1*spoint1.x;
		}else {
			b1 = -spoint1.x;
		}

		double b2 = 0;
		if (spoint2.x!=epoint2.x) {
			b2 = spoint2.y - a2*spoint2.x;
		}else {
			b2 = -spoint2.x;
		}
		
		double yc1 = 0;
		if (spoint1.y!=epoint1.y) {
			yc1 = 1;
		}
		double yc2 = 0;
		if (spoint2.y!=epoint2.y) {
			yc2 = 1;
		}
		
		
		double[][] a ={{yc1,-a1},{yc2,-a2}};
		double[] b = {b1,b2};
		
		double[] fangchengzu1 = F.fangchengzu1(a, b);
		
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				System.out.print(a[i][j]+"  ");
			}
			System.out.println();
		}
		
		for (int i = 0; i < b.length; i++) {
			System.out.println(b[i]);

		}
		
		System.out.println("结果：");
		for (int i = 0; i < fangchengzu1.length; i++) {
			System.out.println(fangchengzu1[i]);
		}
		Point point = new Point();
		point.y = fangchengzu1[0];
		point.x = fangchengzu1[1];
		
		return point;
	}
	

	
	
	
	
	
	
	
	/**
	 * 这种就是只要任意一个点在另一个图的内部，就可以说这两个图是相交的了
	 * 这个算法还有优化的空间，那就是对于图，我们只是需要获取每个图的y值最大点ymax和y值最小点ymin
	 * 用这两个点对一个图进行划分成左右两个线段
	 * 如果图A的ymax和ymin均要小于图B的ymax和ymin，那么我们就只用去判断A图的右线段和B图的左线段是否相交
	 * 
	 * 如果图A的ymax和ymin是部分大于图B的ymax和ymin，那么我们还是需要对所有点进行检查
	 * 这个优化不会减少最坏情况的复杂度，但可以简化最好情况的运算
	 * 
	 * 还有很多的根据情况去判断的优化手段，
	 * 就是知道了ymax的点和ymin的点之后，我们用二分法的方式拿两个线段的中点线段去判断，通过斜率（这个方式是要求两个图都是凸包的图），可以剔除剩下的线段，然后再取剩下的中点
	 * 最后可以达到log(n+m)的复杂度
	 * 这个优化没去实现
	 * 
	 * @param graph0
	 * @param graph1
	 * @return
	 */
	public static boolean graphxiangjiao2(Graph graph0, Graph graph1) {

		List<Line> lines0 = graph0.lines;
		List<Line> lines1 = graph1.lines;
		boolean contain_point01 = contain_point(lines0, lines1);
		if (contain_point01) {
			return true;

		}
		boolean contain_point10 = contain_point(lines1, lines0);
		if (contain_point10) {
			return true;
		}
		
		return false;
	}


	private static boolean contain_point(List<Line> lines0, List<Line> lines1) {
		Map<Point, String> piontmap = new HashMap<>();

		for (int i = 0; i < lines1.size(); i++) {

			piontmap.put(lines1.get(i).spoint, i + "");
			piontmap.put(lines1.get(i).epoint, i + "");

		}
		List<Point> keylist = new ArrayList<>(piontmap.keySet());

		a: for (int j = 0; j < keylist.size(); j++) {
			boolean isleft = false;
			for (int i = 0; i < lines0.size(); i++) {
				Line line = lines0.get(i);
				
				if (i == 0) {
					isleft = ToLeftTest.toLeftTest(line.spoint, line.epoint, keylist.get(j));

					continue;
				}
				if (isleft != ToLeftTest.toLeftTest(line.spoint, line.epoint, keylist.get(j))) {
					continue a;
				}

			}

			return true;

		}
		return false;
	}

	/**
	 * 这种方法是比较呆的，其实我觉得n平方的复杂度，还算是能接受的 不过这种方法，是不认为一个图内包另一个图这种情况是相交的
	 * 
	 * @param graph0 图1
	 * @param graph1 图2
	 * @return
	 */
	public static boolean graphxiangjiao(Graph graph0, Graph graph1) {
		// TODO Auto-generated method stub

		// 先用最SB的方法啊
		List<Line> lines0 = graph0.lines;
		List<Line> lines1 = graph1.lines;

		for (int i = 0; i < lines0.size(); i++) {
			for (int j = 0; j < lines1.size(); j++) {
				Line line0 = lines0.get(i);
				Line line1 = lines1.get(j);

				boolean jiaocha = JiHeQiuJiao.jiaocha(line0, line1);

				if (jiaocha) {
					System.out.println(line0);
					System.out.println(line1);
					return true;
				}
			}

		}

		return false;
	}

	private static List<Graph> initdate() {
		Point[] points1 = new Point[3];

		points1[0] = new Point();
		points1[1] = new Point();
		points1[2] = new Point();
		points1[0].x = 0;
		points1[0].y = 0;

		points1[1].x = 0;
		points1[1].y = 2;

		points1[2].x = 2;
		points1[2].y = 1;

		Point[] points2 = new Point[3];
		points2[0] = new Point();
		points2[1] = new Point();
		points2[2] = new Point();

		points2[0].x = 3;
		points2[0].y = 0;

		points2[1].x = 1;
		points2[1].y = 1;

		points2[2].x = 3;
		points2[2].y = 2;

		Point[] points3 = new Point[3];
		points3[0] = new Point();
		points3[1] = new Point();
		points3[2] = new Point();

		points3[0].x = 4;
		points3[0].y = 0;

		points3[1].x = 6;
		points3[1].y = 0;

		points3[2].x = 5;
		points3[2].y = 2;

		List<Line> lines1 = listline(points1);

		List<Line> lines2 = listline(points2);

		List<Line> lines3 = listline(points3);

		Graph graph1 = new Graph();
		graph1.lines = lines1;

		Graph graph2 = new Graph();
		graph2.lines = lines2;

		Graph graph3 = new Graph();
		graph3.lines = lines3;

		List<Graph> graphs = new LinkedList<>();
		graphs.add(graph1);
		graphs.add(graph2);
		graphs.add(graph3);

		return graphs;

	}

	private static List<Line> listline(Point[] points1) {
		// 生成线段组1
		List<Line> lines1 = new LinkedList<>();
		for (int i = 0; i < points1.length; i++) {
			Line line = new Line();
			line.spoint = points1[i];
			if (i == points1.length - 1) {
				line.epoint = points1[0];
			} else {
				line.epoint = points1[i + 1];

			}
			
			lines1.add(line);

		}
		return lines1;
	}

}
